package com.example.leetdemo.plan1;

import java.util.*;

public class Sword044 {

    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Map<TreeNode, Integer> treeNodeMap = new HashMap<>();
        Map<Integer, Integer> map = new HashMap<>();
        treeNodeMap.put(root, 0);
        map.put(0, root.val);
        queue.offer(root);
        while (queue.peek() != null) {
            TreeNode t = queue.poll();
            Integer height = treeNodeMap.get(t);
            TreeNode p = t.left;
            TreeNode q = t.right;
            if (p != null) {
                treeNodeMap.put(p, height + 1);
                queue.offer(p);
                map.put(height + 1, Math.max(map.getOrDefault(height + 1, p.val), p.val));
            }
            if (q != null) {
                treeNodeMap.put(q, height + 1);
                queue.offer(q);
                map.put(height + 1, Math.max(map.getOrDefault(height + 1, q.val), q.val));
            }
        }
        for (int i = 0; i < map.size(); i++) {
            list.add(map.get(i));
        }
        return list;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
